\section{Introduction}
\label{sec:intro}
Diffusion processes defined on networks are general models used in a
number of applications, as illustrated in Table \ref{table:example}.
Despite the diversity among these applications, there are fundamental
similarities in the mathematical models and questions of interest,
such as: understanding the dynamics (e.g., will a disease become an
epidemic and who would get infected), and designing interventions to
control the dynamics (e.g., how to vaccinate or quarantine the
population so that the epidemic is controlled, or how to add resources
so that the network is resilient).  These interventions often
translate to voluntary directives (e.g., to take vaccines or stay
home) from government or public agencies; however, people do not
always adhere to such recommendations, and make individual decisions
based on their specific utilities and objectives. Additionally, people
alter their contacts dynamically, and these behavioral changes have a
huge impact on the dynamics and the effectiveness of these
interventions, so that ``good'' intervention strategies might, in
fact, be ineffective, depending on the behavioral changes. Such interactions and
decisions happen in a very decentralized manner, which makes game theory a
natural approach to study these problems, and is the basis of our proposal.

\begin{table}[htb]
\begin{center}
\begin{small}
%\begin{tabular}{|p{0.7in}||p{1.0in}|p{0.7in} | p{0.7in}|p{1.25in}|p{1.25in}|}
\begin{tabular}{|c||c|c | c|c|c|}
\hline
\textbf{Application} & \textbf{Agents} & \textbf{Network} & \textbf{Diffusion model} & 
\multicolumn{2}{|c|}{\textbf{Strategies}}\\ 
& & & & \textbf{Intervention} & \textbf{Behavior}\\ \hline \hline
Human & People & social contact & SIR/SIS \cite{Ne03} &
Vaccinate & Social \\
diseases & &  networks & & risky behavior & distancing\\ \hline
Animal  & Farms & Geometric network & SEIR with  & Vaccinate livestock & Resource\\ 
diseases & & & distance kernel \cite{bruhn07} & Quarantine farm&  sharing\\\hline
Malware & Users, Computers & Router graph & SIS \cite{berger+episcalefree05} &
Install patches & Clicking \\ 
& Sysadmins & & & &on links\\\hline
Viral  & Users, Companies & Social and  & Threshold  &
Buy/gift product & Emulating \\ 
marketing & & online networks & models 
\cite{KempeKT03} & & neighbors\\ \hline
\end{tabular}
\caption{Examples of diverse contagion applications.}
\label{table:example}
\end{small}
\end{center}
\end{table}

\BfPara{The role of space and time} The goal of this project is to 
study the spread and control of contagion. 
By space we mean the structure of the network both at the local 
and global scales. Network structure has a direct effect on both 
the spread of information as well as the nature of interactions, as has been observed
by a number of researchers, e.g., \cite{Ne03, jackson10}.
Different strategic agents (e.g., diseases and viruses) have 
always been cognizant (implicitly or 
explicitly) of the underlying networks and have in fact evolved 
schemes to manipulate and exploit the network structure in 
furtherance of their individual ends. The local interests and 
constraints of the individual players are reflected in the 
dynamics and global structure of the resulting complex systems.  
These interests and constraints affect the evolution of the 
network as well as the equilibrium it tends towards.

By time we mean the temporal aspects of the spread of behavioral 
change and interventional control both in oblivious and adaptive 
contexts. Individuals can decide whether and when to take certain 
actions. These actions could be behavioral (e.g., increasing the 
frequency or intensity of contacts with others) or interventional
(e.g., taking a vaccine or installing anti-virus software). 
Further the actions could be oblivious, i.e., independent of
the evolution of the contagion and the decisions of others,
or they could be adaptive incorporating the events of the past
and the actions of the others (e.g. looking at Google Flu Trends
before deciding to get a flu shot).

In general, of course, problems involve both spatial and temporal aspects.
The tasks we propose are summarized below, and are formulated in terms of 
non-cooperative games.

\iffalse
The situations we propose to model and study in this proposal will,
in general, have both spatial (involving information and interaction)
and temporal (both oblivious and adaptive) aspects. In order to
develop our intuition we will study and analyze simpler cases in
which one or more of these aspects have been eliminated. It is our
hope that this will yield insights that will enable us to tackle
the more complex cases that capture real-world issues more 
accurately. In addition to studying non-cooperative games, we 
will also consider hybrid models where a subset or subgroup
of the individuals are given preference, while the remaining 
population makes individual decisions based on perceived utility.
The study of such Stackelberg equilibria and their properties will 
yield useful public policy guidelines for prioritizing interventions.
 

\BfPara{Research Methodology}
We propose a methodological framework for studying the spread and
control of contagion that integrates three key ingredients:
percolation theory, widely used in epidemiology and dynamical systems;
algorithmic game theory for modeling individual decision-making and
studying resulting equilibria; tools from complex networks to model
and analyze social contacts. Algorithmic game theory is of particular
relevance to us in this project because we propose going beyond
descriptions and principles of formation; our goal is to suggest
prescriptive policies that will impact the complex network in ways
that improve the human condition. Naturally a policy whose actions or
consequences are not efficiently computable has little meaning and
this is why the tools and techniques of algorithmic game theory are a
great match for pursuing this program. We plan to consider random 
graph models, as well as application-specific models such as human 
contact networks for epidemiology, farm networks that take into 
account movement of animals or farm equipment, and communication 
networks~\cite{Ne03, EG+04}. 

The problems we plan to study are complex and will require us to
approach them with multiple lenses and at multiple scales.  We believe
that an appropriate combination of tools from game theory, dynamical
systems, complex networks and large scale agent based simulations will
yield substantial new insights to how contagions spread and how best
to control them.  In the course of this project, we will also draw
connections between the diverse models and techniques we will use.  
While we plan to focus largely on
questions in epidemiology, the mathematical and computational methods
we will develop apply to a wider class of stochastic diffusion
processes, such as viral marketing and gossip algorithms. 
\fi

\subsection{Space: the network as a battleground} 
Individual intervention decisions (e.g.,
vaccination, quarantining, anti-virus software, etc.,) 
are based on ``information'' about a variety of
factors such as the cost and perceived efficacy of the intervention,
the current rate of infection and extent of intervention.  Individuals
alter their behavior in significant and sometimes unconscious ways,
during the course of an epidemic (e.g., people might reduce avoidable
contacts depending on the perceived risk of infection as in the
case of H1N1), or, sometimes increase their contacts after getting
vaccinated (based on overestimation of the efficacy of vaccines),
thereby altering the underlying ``interactions''; see, e.g., \cite{jackson+y:diffusion,jackson10,galeotti+gjvy:network}.  The complex
\emph{interactions} and \emph{information} exchange patterns often
lead to unexpected effects, e.g., risky behavior in the form
of increased contacts by people who get vaccinated by a vaccine with
limited efficacy leads to the perverse outcome that as more
people are vaccinated, the expected outbreak size \emph{increases}
(as shown in \cite{blower+risk94} for HIV); in preliminary work, we
have shown the network structure can amplify these effects \cite{kumar+rss:moral}.

\BfPara{Locality of information} The spread of a disease or contagion
and the intervention strategies that emerge crucially depend on the
amount and quality of information available to the individuals.  From
a spatial perspective, the amount of the information available can be
characterized by its locality: the distance $d$ within the network up
to which information is available to the node ($d$-local); our
preliminary results \cite{kumar+rss:icdcs} (and analogous results of
Galeotti et al.~\cite{galeotti+gjvy:network}) suggest that $d$ has a
big influence on the existence and structure of equilibria.  \iffalse
In addition to its local nature, the information available to a node
may be imperfect.  We will capture imperfect information through
Bayesian methods and models involving aggregate data.  In preliminary
work \cite{kumar+rss:icdcs}, we have analyzed simple game-theoretic
models that apply both to anti-virus software installations and
vaccinations.  We have found that the amount of information used in
the individual utility function has significant consequences on the
existence and structure of equilibria.  \fi Specific questions of our
research study include:
\begin{itemize}
\item
Under what conditions do pure Nash equilibria exist for intervention
games in which the information available to each node is $d$-local?
What is the complexity of finding these and mixed equilibria?  What is
the structure of mixed equilibria: are they stable (robust to
perturbations), unique, how do they compare to the social optimum?
From a social optimum standpoint can less information ever be better than more?
\end{itemize}

\BfPara{Connection-altering interactions} We will consider models where a node may
change its interactions with neighbors in a simple local manner, based
on perceived information about an ongoing epidemic, or after an
intervention.  Such behavioral changes in interactions lead to altered
contacts and changes in the rate of spread of the contagion.  Together
with the possibility that all interventions may not succeed, this
results in a complex dynamic process.  
\iffalse
The fundamental problem in this
context is to understand the impact of behavioral changes on the
spread of contagions, and to determine effective intervention
strategies. In preliminary work we have been able to show that the nature
 of the interaction has dramatic effects on the success of vaccination campaigns.
In particular we have discovered less vaccination can be more effective both
for one-sided (or Type I) diseases such as H1N1 (influenza) as well as
two-sided (or Type II) diseases such as HIV, but in dramatically different ways.
\fi
Specific questions we propose include:
\begin{itemize}
\item How is the structure of the network affected by the interplay
between the strategic agents? In turn, how does the network
structure play a role in placing constraints and modifying the
interests and actions of the strategic players?  How can we control
the dynamics and evolution of the complex network in order to
achieve a more favorable societal outcome?
\end{itemize}

\subsection{Time: a tool of strategy}
The decision of whether and when to adopt an interventional strategy 
or exercise a behavioral choice can play a crucial role in the spread
or containment of a contagion. 

\BfPara{Oblivious strategies} In the case of fast-moving contagions 
individuals may be forced to adopt oblivious strategies based on Bayesian 
models of past outbreaks or estimates of the behaviors of those in their 
contact network. Similarly, public policy tools that require long lead-times 
to deploy and to become effective will require the adoption of 
premeditated action plans.
In~\cite{reluga:plos10}, we have investigated how the decisions based on past
epidemic sizes can combine with contact network structure and lead to
erratic flu vaccination behavior.  
\begin{itemize}
\item
When do there exist Nash equilibria with Bayesian priors? What are
simple and natural thumb-rules adopt-able by individuals to contain the 
spread of contagion? Is it conceivable that we can afford the most vulnerable
segments of a population greater protection by dispensing more vaccine to the 
stronger or invulnerable segments? 
\end{itemize} 

\BfPara{Adaptive strategies} In order to control the spread of a
contagion within an evolving network, it is both critical and natural
that the intervention strategies themselves be dynamic -- critical,
from a public policy standpoint; natural for an individual to include
the time dimension in their strategy space.  With time, each player
may acquire greater and more accurate information about the network
and the contagion, enabling a more effective intervention strategy. We
have formulated simplified vaccination games where strategies capture
the temporal aspect of when an individual may choose to vaccinate or
adopt behavior changes such as social
distancing~\cite{reluga:mbs10,reluga:plos10}.
\begin{itemize}
\item
What is the interplay between the spread of the contagion and the 
spread of the intervention? What factors determine when the interventional 
strategy will overcome the contagion? When can the anti-virus software
outrun the virus?
\end{itemize}

\subsection{Intellectual Merit and Novel Contributions}

While there is a huge literature on network games and contagion
processes (see Section~\ref{sec:related} for a review of related
work), there are several fundamental differences between our proposed
project and this line of previous research: (i) the focus of our work
is on the {\em impact of centralized and decentralized intervention
  strategies on the spread of contagion}, rather than analyzing how
contagions spread; (ii) we take into account {\em changes in the
  network} in the course of the diffusion process, and (iii) we
consider a much {\em richer strategy space}\/ which takes into account
temporal issues (when an intervention is adopted) and the nature of
the interventions.  As noted by Jackson and Yariv \cite{jackson10}, a
big shortcoming in the network games literature is ``... that the
foundation for modeling the underlying network is rooted in simple
forms of random graphs in which there is little heterogeneity among
nodes other than their connectivity.''  We address this by bringing
together three key ingredients: percolation theory, widely used in
epidemiology and dynamical systems; algorithmic game theory for
modeling individual decision-making and studying resulting equilibria;
tools from complex networks to model and analyze the rich
heterogeneity of social contacts. Our end goal is to analyze and guide
public health policy decisions though such a framework.
Though we discuss most of the problems in the context of epidemics, the questions, and
many of the results will extend to other applications and models
discussed in Table \ref{table:example}.

\iffalse
Algorithmic game theory is of particular
relevance to us in this project because we propose going beyond
descriptions and principles of formation; our goal is to suggest
prescriptive policies that will impact the complex network in ways
that improve the human condition. Naturally a policy whose actions or
consequences are not efficiently computable has little meaning and
this is why the tools and techniques of algorithmic game theory are a
great match for pursuing this program. We plan to consider random 
graph models, as well as application-specific models such as human 
contact networks for epidemiology, farm networks that take into 
account movement of animals or farm equipment, and communication 
networks~\cite{Ne03, EG+04}. 

The problems we plan to study are complex and will require us to
approach them with multiple lenses and at multiple scales.  We believe
that an appropriate combination of tools from game theory, dynamical
systems, complex networks and large scale agent based simulations will
yield substantial new insights to how contagions spread and how best
to control them.  In the course of this project, we will also draw
connections between the diverse models and techniques we will use.  
While we plan to focus largely on
questions in epidemiology, the mathematical and computational methods
we will develop apply to a wider class of stochastic diffusion
processes, such as viral marketing and gossip algorithms. 
\fi

\subsection{Expected Contributions and Broader Impact}
At a high-level the goals of this project are three-fold: (1) we will
give intellectual unity to the study of contagion by providing a
general framework for the problem space and a collection of techniques
arrayed from the three principal areas of percolation theory,
algorithmic game theory and complex networks; (2) we will provide
policy makers a scaffolding in which to embed their datasets and frame
their hypotheses and simulations with the ultimate aim of providing
greater health benefits for society; and (3) we hope to provide
greater insight into the true choices that individuals possess and the
power they can exert by exercising those choices.

Our project provides exciting research opportunities for both graduate
and undergraduate students, and for meaningful collaborations with a
number of other researchers. The PIs' teaching interests are aligned
with the research topics of this proposal, thus allowing for
significant curriculum development. The project has potential for
interesting work in data gathering and simulation by undergraduates
and strong dissertation work at the intersection of computer science,
complex networks, epidemiology, and game theory.

\subsection{Research Team and Strengths}  
Our multidisciplinary team consists of PI Ravi Sundaram (Northeastern
University) and co-PIs Rajmohan Rajaraman (Northeastern University),
Tim Reluga (Penn State University), and Anil Vullikanti (Virginia
Tech), and Zhengzheng Pan, a postdoctoral associate at Virginia Tech.
Sundaram is a computer scientist with experience in complexity
theory, algorithmic game theory, networks and security.  Rajaraman is
a computer scientist with experience in algorithmic game theory,
approximation algorithms and distributed computing.  Reluga is a
mathematical epidemiologist, with experience in the use of game theory
in epidemiology.  Vullikanti is a computer scientist with experience
in wireless networks, complex networks and agent based simulations.
Pan is an economist and has studied game theoretical models for
contagion models.

The PIs' previous work has led to important advances in the areas of
networks and epidemiology.  As Director of Engineering at Akamai
Technologies (prior to Northeastern), Sundaram was a key architect of
their massive content delivery network; he was responsible for their
mapping of browser requests (over 10 billion a day) to the optimal
server.  Rajaraman's joint work related to distributed hash
tables~\cite{plaxton+rr:access} is widely-cited and has been
implemented in prototype peer-to-peer networks. Reluga's research has
brought together rigorous mathematical epidemiology and game theory,
including an analysis of current public health policies for influenza
from this perspective \cite{galvani+rc:influenza07}. Vullikanti's joint
work includes analysis of disease dynamics and interventions for
large urban populations \cite{EG+04}.  Together, the team
has expertise in theoretical computer science, combinatorial
optimization, game theory, mathematical epidemiology, dynamical
systems and agent based simulations for socio-technical systems, and
is well qualified for the problems being addressed in this project.

\junk{
We will develop game-theoretic models that consider the time-evolving
nature of the problem.  For instance, the decision of an individual
may depend not only on extent of the current outbreak, but also on the
efficacy of vaccinations in thwarting outbreaks of previous years.


Our framework will extend the formulation in Topic 1 to a game
theoretical setting, in which individuals decide on interventions
based on perceived utility.  We will consider utility functions that
take into account limited information available to most individuals,
e.g., the extent of the current outbreak and intervention decisions
(e.g., from nodes within a $d$-neighborhood, or estimates of the
overall outbreak).  We will also consider, when appropriate, the
competing interests of the agents (e.g., among live-stock owners and
department of agriculture in the case of spread of animal diseases).
The main goal is to understand the structure of equilibria in such
non-cooperative games, and the impact of various parameters on their
structure and efficiency.

In~\cite{reluga:plos10}, we have investigated how the decisions based on past
epidemic sizes can combine with contact network structure and lead to
erratic flu vaccination behavior.
\end{itemize}

\subsection{Expected contributions}



This is the d = finite vs d = infinity
case (ICDCS paper).  As future problems, we should also add Bayesian
information as opposed to perfect information within the d
neighborhood or some hybrid version.  The strategy space could be
binary or generalization with multiple levels and costs.

-- Connections: Now we add to the strategy space the possibility of
adding/deleting connections.  The argument is that interventions will
naturally be accompanied with connection changes when players do their
cost-benefit analysis.  This is building on our moral hazard work,
which we can state as preliminary work.

-- Time: Now we add to the strategy space the time at which
intervention can be done.  Here we can first formulate without the
connections aspect of the strategy space.  Mention Reluga's work.  And
then also define more general problems.  This will probably be the
most speculative.

In each case, we will look at both equilibria as well as from a public
policy standpoint (Stackelberg or social optimum).



Our proposed research is organized along
three dimensions: locality of information, evolving connections, and
temporal strategy spaces.


The team members have developed and used game theoretical
analysis in a variety of applications, including networking
\cite{...}, diffusion processes \cite{...}, and have also used this to
evaluate public health policies \cite{..}.

The team brings together techniques from random graph
theory and combinatorial optimization with continuous differential
equation based approaches, allowing it to tackle multi-scale problems
in disease transmission.

Diffusion processes defined on networks are general models used in a
number of applications, such as (i) disease transmission in human
contact networks or among livestock in farm networks, (ii) spread of
malware in communication networks, (iii) stochastic failures in
infrastructure networks, and (iv) spread of information, fads and
viral marketing. Despite the diversity among these applications, there
are fundamental similarities in the mathematical models and questions
of interest, such as: understanding the dynamics (e.g., will a disease
become an epidemic and who would get infected), and designing
interventions to control the dynamics (e.g., how to vaccinate or
quarantine the population so that the epidemic is controlled, or how
to add resources so that the network is resilient). These
interventions often translate to voluntary directives (e.g., to take
vaccines or stay home) from government or public agencies; however,
people do not always adhere to such recommendations, and make
individual decisions based on their specific utilities and
objectives. Additionally, people alter their contacts dynamically, and
these behavioral changes have a huge impact on the dynamics and the
effectiveness of these interventions, so that ``good'' intervention
strategies might become sub-optimal, depending on the behavioral
changes.

The goal of this project is to study the impact of information and
interaction on the spread and control of contagions.  A contagion
spreads through ``interactions'' in a contact network whose properties
have a significant impact on the extent and dynamics of the spread.
We plan to consider random graph models, as well as
application-specific models such as human contact networks for
epidemiology, farm networks that take into account movement of animals
or farm equipment, and communication networks~\cite{Ne03, EG+04}.
Contagions are often controlled by a variety of interventions, e.g.,
vaccination, quarantining, anti-virus software, etc.  Individual
intervention decisions are based on ``information'' about a variety of
factors such as the cost and perceived efficacy of the intervention,
the current rate of infection and extent of intervention. Individuals
alter their behavior in significant and sometimes unconscious ways,
during the course of an epidemic -- people might reduce avoidable
contacts depending on the perceived risk of infection (e.g., as in the
case of H1N1), or, sometimes increase their contacts after getting
vaccinated (based on overestimation of the efficacy of vaccines),
thereby altering the underlying ``interactions''.  The complex
\emph{interactions} and \emph{information} exchange patterns often
lead to unexpected effects.  For instance, risky behavior in the form
of increased contacts by people who get vaccinated by a vaccine with
limited efficacy could lead to the following perverse outcome: as more
people are vaccinated, the expected outbreak size \emph{increases},
instead of going down; this has been observed in the case of HIV
\cite{blower+risk94}.

We propose a methodological framework for studying the spread and
control of contagions that integrates three key ingredients:
percolation theory, widely used in epidemiology and dynamical systems;
algorithmic game theory for modeling individual decision-making and
studying resulting equilibria; tools from complex networks to model
and analyze social contacts.  Our research brings together a range of
issues and techniques from computer science, economics and sociology,
making it a good fit for the NSF ICES program solicitation.
While these issues have been identified and studied empirically,
  there is very limited theoretical understanding of their impact on
  diffusion processes.


The transmission of diseases is commonly modeled as a stochastic
diffusion process on a network. A central concern in public health
policy planning is the control of disease transmission by means of
vaccination, quarantining and social distancing guidelines.
Implementing these interventions is a challenging problem involving
optimal resource allocation, economic incentives and pricing,
individual decision making and many sociological issues.  For
instance, there is a shortage of vaccines every year, often leading to
a contentious debate over who should be vaccinated, and if mandatory
vaccination of a sub-population would be appropriate \cite{...}.
While these problems involve fundamental philosophical and social
issues, a key impediment in this debate is the lack of adequate
mathematical and computational tools to analyze and compare different
strategies.  For instance, school closure is often found to be a good
strategy in controlling disease spread \cite{halloran:pnas08}; however,
this has huge economic implications, and often the debate is clouded
by lack of adequate understanding of the models and quantitative data
about them.



Let $G=(V,E)$ denote a contact network, which is an abstract model of
contacts between set $V$ of agents, such as: (i) the human contact
network, where $V$ is a set of people, (ii) the farm network, where
$V$ is the set of farms, with edges representing potential contacts
between the farms (involving movement of animals or farm equipment,
which could spread disease), and (iii) a communication network, where
$V$ is the set of nodes, and $E$ is the set of links along which worms
or viruses may spread. The network properties have significant impact
on the dynamics, and  \cite{Ne03, EG+04}.  

If node $v$ gets
vaccinated successfully, it is assumed not to get infected and could
be removed from $G$.  A crucial element of this project is to quantify
the impact of partial efficacy of vaccines; the efficacy of a vaccine
can be captured by a success probability that may depend on the node,
the type of vaccine, and may even vary with time.



Game theory is a natural approach to study individual
decision making in the context of vaccination. An important criticism
in the practicality of non-cooperative game theory has been the
difficulty in evaluating the individual utility functions; even if we
ignore the computational complexity, the amount of information needed
to estimate the utility functions is challenging. 



At a high level, the focus problems of this project can be broken down
into two categories.

\smallskip

\noindent
\textbf{Topic 1. Impact of interaction: behavioral changes}.  We will
consider models where a node may change its interactions with
neighbors in a simple local manner, based on perceived information
about an ongoing epidemic, or after an intervention.  Such behavioral
changes in interactions lead to altered contacts and changes in the
rate of spread of the contagion.  Together with the possibility that
all interventions may not succeed, this results in a complex dynamic
process.  The fundamental problem in this context is to understand the
impact of behavioral changes on the spread of contagions, and to
determine effective intervention strategies. Specific questions
include:
\begin{itemize}
\item
For a given contact network, intervention efficacy and policy,
transmission model, and behavioral change pattern, how does the extent
of intervention affect the expected size of the epidemic and its
dynamics?  We expect to use tools from percolation theory and
stochastic diffusion to categorize the different regions of the
problem space.

\item
For a given contact network and behavioral change pattern, what is an
optimal intervention?  Given costs for intervention for affecting
behavioral changes, how should resources be allocated to minimize the
impact of the contagion?  How can we do surveillance to detect a rare
but potentially expensive outbreak?  These lead to new classes of
stochastic optimization problems for networks.

\item
We also consider extensions of this model, in which intervention
decisions are not all made simultaneously at the start of the process,
but in a staged manner.
\end{itemize}


consider the following model: each node $v$ in a subset $S\subset V$
of nodes changes its interactions (with some or all neighbors) in a
simple local manner, .  The changes in
interactions (or behavioral changes) lead to altered contacts and
transmission probabilities according to the following models (and
their hybrid versions): (i) in the ``1-sided'' model (which captures
diseases such as H1N1), the transmission probability on each edge
incident on $v\in S$ is increased, while in (ii) the ``2-sided'' model
(which captures diseases such as HIV), the transmission probability is
increased only on edges $e=(u,v)$ with both end-points $u,v\in S$.


In ongoing work in epidemiology, we have discovered counterintuitive
non-monotonicity phenomena that arise as a consequence of the complex
interplay among vaccine inefficacy, behavioral changes, and network
structure~\cite{kumar+rss:moral}.  In our study, we adopt the widely
used SIR model of disease transmission, in which each infected node
spreads the disease to each neighbor (which is initially susceptible)
with a fixed probability, independent of other transmissions.  We
consider different behavioral models: for instance, in the ``1-sided''
model (which captures diseases such as H1N1), a contact is affected
when any one of the endpoints changes their behavior, while in the
``2-sided'' model (which captures diseases such as HIV), a contact is
only affected when both endpoints change behaviors.  Assuming that
vaccines fail with some non-zero probability, we find that the
perverse outcomes alluded to above -- ``less vaccination can lead to
more infections'' -- take rich and complex forms, depending on the
behavioral model and network.  For instance, the 1- and 2-sided models
have complementary characteristics, and in some cases, random
vaccinations beat targeted ones.
%We have also studied the impact of behavior changes such as
%social distancing on the extent of an epidemic~\cite{Tim}.


An infected node remains infectious for a certain
period and then recovers. Interventions (such as vaccination or
quarantining) can be modeled by graph changes: if a node $v$ is
vaccinated successfully, all incident edges $(v,u)\in E$ are removed,
while quarantining can be modeled by the deletion of a subset
$E'\subseteq E$ of edges.  


\smallskip

\noindent
\textbf{Topic 2. Impact of information: individual decision making}.
Our framework will extend the formulation in Topic 1 to a game
theoretical setting, in which individuals decide on interventions
based on perceived utility.  We will consider utility functions that
take into account limited information available to most individuals,
e.g., the extent of the current outbreak and intervention decisions
(e.g., from nodes within a $d$-neighborhood, or estimates of the
overall outbreak).  We will also consider, when appropriate, the
competing interests of the agents (e.g., among live-stock owners and
department of agriculture in the case of spread of animal diseases).
The main goal is to understand the structure of equilibria in such
non-cooperative games, and the impact of various parameters on their
structure and efficiency.
\begin{itemize}
\item
Under what conditions do pure Nash equilibria exist for these
intervention games?  What is the complexity of finding these and mixed
equilibria?  What is the structure of mixed equilibria: are they
stable (robust to perturbations), unique, how do they compare to the
social optimum?

\item
We plan to consider hybrid models where a subset or subgroup of the
individuals are given preference, while the remaining population makes
individual decisions based on perceived utility.  The study of such
Stackelberg equilibria and their properties will yield guidelines for
prioritizing interventions.

\item
We will develop game-theoretic models that consider the time-evolving
nature of the problem\junk{, both in terms of changes in decisions as
  an outbreak evolves, as well as the annual nature of some disease
  incidences.}  For instance, the decision of an individual may depend
not only on extent of the current outbreak, but also on the efficacy
of vaccinations in thwarting outbreaks of previous years.
\end{itemize}
In preliminary work \cite{kumar+rss:icdcs}, we have analyzed simple
game-theoretic models that apply both to anti-virus software
installations and vaccinations.  We have found that the amount of
information used in the individual utility function has significant
consequences on the existence and structure of equilibria.



\smallskip
The problems we plan to study are complex and will require us to
approach them with multiple lenses and at multiple scales.  We believe
that an appropriate combination of tools from game theory, dynamical
systems, complex networks and large scale agent based simulations will
yield substantial new insights to how contagions spread and how best
to control them.  In the course of this project, we will also draw
connections between the diverse models and techniques we will use
(e.g. between the SIR model with differential-equation based
techniques on one hand and random graph models and probabilistic
techniques on the other).  While we plan to focus largely on questions
in epidemiology, the mathematical and computational methods we will
develop apply to a wider class of stochastic diffusion processes, such
as viral marketing and gossip algorithms.


Interaction and
information are inherent in such applications as well, and the results
we obtain are likely to extend to these areas as well. In order to
make our project feasible, and well scoped, we will study random graph
models, and will combine analytical as well as simulation based
approaches.  Additionally, our models are ``local'', with simple, yet
realistic aspects of the underlying problem.


\smallskip
\noindent
\textbf{Research Team and Strengths}. The team consists of Rajmohan
Rajaraman and Ravi Sundaram (Northeastern University), Anil Vullikanti
(Virginia Tech) and Tim Reluga (Penn State University).  Rajaraman and
Sundaram are computer scientists with specializations in distributed
computing and game theory, and networks, respectively. Vullikanti is a
computer scientist with experience in wireless networks, complex
networks and agent based simulations. Reluga is a mathematical
epidemiologist, with experience in the use of game theory in
epidemiology.  Together, the team has expertise in theoretical
computer science, combinatorial optimization, game theory,
mathematical epidemiology, dynamical systems and agent based
simulations for socio-technical systems, and is well qualified for the
problems in this proposal.  The team members have developed
and used game theoretical analysis in a variety of applications,
including networking \cite{...}, diffusion processes \cite{...}, and
have also used this to evaluate public health policies \cite{..}.

The team brings together techniques from random graph
theory and combinatorial optimization with continuous differential
equation based approaches, allowing it to tackle multi-scale problems
in disease transmission.

}

